package practice;


import java.util.*;

public class Day27 {
    static class LRUCache {
        LinkedHashMap<Integer, Integer> map;
        int size = 0;
        public LRUCache(int capacity) {
            map = new LinkedHashMap<>(capacity, 0.5f, true);
            size = capacity;
        }
        private boolean isFull() {
            return size < map.size();
        }
        public int get(int key) {
            int ret = map.getOrDefault(key, -1);
            return ret;
        }

        public void put(int key, int value) {
            map.put(key, value);
            if(isFull()) {
                for(Map.Entry entry : map.entrySet()) {
                    map.remove(entry.getKey());
                    break;
                }
            }
        }
    }
    //环形链表问题
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        while(slow != fast || slow == 0) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        slow = 0;
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

    //栈的相关题
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] ret = new int[temperatures.length];
        for(int i = 0; i < temperatures.length; i++) {
            if(stack.isEmpty()) {
                stack.push(i);
            }else {
                while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                    int topIndex = stack.pop();
                    ret[topIndex] = i - topIndex;
                }
                stack.push(i);
            }
        }
        return ret;
    }
    //完全平方数
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j*j <= i; j++) {
                dp[i] = Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
    //零钱兑换
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp = new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for(int i = 1; i <= amount; i++) {
            for(int j = 0; j < n; j++) {
                if(i - coins[j] >= 0) {
                    dp[i] = Math.min(dp[i],dp[i-coins[j]] + 1);
                }
            }
        }
        return dp[amount] == amount+1 ? -1 : dp[amount];
    }
    //乘积最大子数组
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] f = new int[n+1];
        int[] g = new int[n+1];
        f[0] = 1;
        g[0] = 1;
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            f[i] = Math.max(nums[i-1] > 0 ? f[i-1] * nums[i-1] : g[i-1] * nums[i-1],nums[i-1]);
            g[i] = Math.min(nums[i-1] > 0 ? g[i-1] * nums[i-1] : f[i-1] * nums[i-1],nums[i-1]);
            max = Math.max(f[i],max);
        }
        return max;
    }

    //分割等和数据集
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }
        if (sum % 2 == 1) {
            return false;
        } else {

            sum /= 2;
            boolean[][] dp = new boolean[n + 1][sum + 1];
            for (int i = 0; i <= n; i++) {
                dp[i][0] = true;
            }
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= sum; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (j - nums[i - 1] >= 0) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
                    }
                }
            }
            return dp[n][sum];
        }
    }
}
